package findindexsubstring28

// KMP 算法
// 1. 构建部分匹配表（前缀表）
// 2. 遍历 haystack 和 needle，使用部分匹配表进行匹配
// 3. 如果匹配成功，返回匹配的起始位置
// 4. 如果匹配失败，使用部分匹配表跳过一些不必要的比较
// 5. 时间复杂度 O(n+m)，空间复杂度 O(m)
// 6. 注意：部分匹配表的长度为 needle 的长度
// 7. 注意：部分匹配表的值表示当前字符与前缀的最长公共前缀的长度
func strStrKmp(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}
	if len(needle) > len(haystack) {
		return -1
	}

	// 构建部分匹配表
	// 即传统的next数组，长度就是模式串的长度
	prefix := make([]int, len(needle))
	j := 0
	for i := 1; i < len(needle); i++ {
		for j > 0 && needle[i] != needle[j] {
			j = prefix[j-1]
		}
		if needle[i] == needle[j] {
			j++
		}
		prefix[i] = j
	}

	j = 0
	for i := 0; i < len(haystack); i++ {
		for j > 0 && haystack[i] != needle[j] {
			j = prefix[j-1]
		}
		if haystack[i] == needle[j] {
			j++
		}
		if j == len(needle) {
			return i - j + 1
		}
	}

	return -1
}

// 使用自定义的 getNext方法来实现 KMP 算法
func strStrKmp2(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}
	if len(needle) > len(haystack) {
		return -1
	}

	next := getNext(needle)

	// 遍历haystack
	j := 0 // needle 的指针
	// 每一个i位置都尝试与模式串的j位置的字符进行对比，如果最后发现模式串全都参与了对比，说明有子串
	for i := 0; i < len(haystack); i++ {
		// 将 haystack[i] 和 needle[j] 进行比较
		// 如果二者相等，j要向后移动去和i++对比
		// 如果不相等，j要回溯到 next[j] 的位置
		for haystack[i] != needle[j] {
			// 如果 j == 0，说明没有相同的前后缀了，跳出循环，让 i++，继续对比下一个字符
			if j == 0 {
				break
			}
			j = next[j]
		}

		// 找到了和当前i位置的字符相同的字符，那么就将 j++，继续对比下一个字符
		if haystack[i] == needle[j] {
			j++
		}
		// 如果 j == len(needle)，说明找到了子串，因为j的最大值是 len(needle)-1
		if j == len(needle) {
			// 返回子串的起始位置
			return i - (len(needle) - 1)
		}

	}
	return -1
}

func getNext(pattern string) []int {
	if len(pattern) == 0 {
		return []int{}
	} else if len(pattern) == 1 {
		return []int{-1}
	} else if len(pattern) == 2 {
		return []int{-1, 0}
	}
	// 使用动态规划的方式计算 next 数组
	// next[i] 表示模式串 pattern[0:i] 的最长相同前后缀的长度
	// next[0] = -1
	// 状态转移方程：
	// next[i] 依赖 next[i-1] 和 pattern[i-1]
	// 如果 pattern[i] == pattern[next[i-1]]，则 next[i] = next[i-1] + 1
	// 否则，要对 next[i-1] 进行回溯，直到找到一个相同的前后缀
	// 1. 初始化 next 数组
	// 2. 遍历 pattern，计算 next 数组
	//   2.2 关键是如何进行回溯。
	// 		j = next[i-1]，表示当前字符与前缀的最长公共前缀的长度。
	//      如果是简单回溯的话，我们就基于 j-1 的长度继续进行前后缀的比较即可，然后是 j-1-1，直到为0.
	//      但是这样就无法使用上我们之前的计算数据了，因为 j 的两侧实际上是一一映射的两个子串，我们只要退回到 next[j] 的位置，重新匹配即可。
	next := make([]int, len(pattern))
	next[0] = -1
	next[1] = 0
	for i := 2; i < len(pattern); i++ {
		if pattern[i-1] == pattern[next[i-1]] {
			// 第一个转移方程就是可以直接使用上一个的 next[i-1] + 1
			next[i] = next[i-1] + 1
		} else {
			// 第二个转移方程就是要进行回溯了
			// 1. 先将 j 赋值为 next[i-1]
			j := next[i-1]
			// 2. 然后进行回溯，直到找到一个相同的前后缀
			for j >= 0 && pattern[i-1] != pattern[j] {
				j = next[j]
			}
			// 3. 如果找到了相同的前后缀，就看一下此时的 j+1 处的值和 i-1处的值是否相同
			if j > 0 && pattern[i-1] == pattern[j] {
				// 如果相同，就将 next[i] 赋值为 j + 1
				next[i] = j + 1
			} else {
				// 如果不相同，就将 next[i] 赋值为 0
				next[i] = 0
			}
		}
	}

	return next
}
